#pragma once
#include <list>
#include <unordered_map>
/*
Implement the LRU algorithm to cache file access lists
*/
namespace BackupFS
{
    template<typename K, typename V>
	class BackupFSLRU
	{
       
        private:
            std::list<std::pair<K, V>> cache;
            std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> cacheMap;
        public:
            BackupFSLRU() {}
            virtual ~BackupFSLRU() 
            {
                cache.clear();
                cacheMap.clear();
            }
            void Remove(const K& key)
            {
                auto it = cacheMap.find(key);
                if (it != cacheMap.end()) 
                {
                    cache.erase(it->second);
                    cacheMap.erase(it);
                }
            }
            LONGLONG Size()
            {
                return cache.size();
            }
            // remove the last item
            K RemoveLast(bool &removed)
            {
                auto last = cache.end();
                last--;
                K key = last->first;
                /*if (time(NULL) - last->second <= 3)
                {
                    removed = false;
                    return key;
                }*/
                cacheMap.erase(last->first);
                cache.pop_back();
                removed = true;
                return key;
            }
            // add or update an item
            void Update(const K& key, const V& value) 
            {
                auto it = cacheMap.find(key);
                if (it != cacheMap.end()) 
                {
                    cache.erase(it->second);
                    cache.push_front(std::make_pair(key, value));
                    cacheMap[key] = cache.begin();
                }
                else 
                {
                    cache.push_front(std::make_pair(key, value));
                    cacheMap[key] = cache.begin();
                }
            }
	};
}

